Authentication schemes have been used in various situations.
Further, authentication schemes using various algorithms have been developed. As a technology related to a Multivariate Quadratic (MQ) authentication scheme (a scheme based on an MQ question), a technology disclosed in Non-Patent Literature 1 below is exemplified. As a technology related to a Multivariate Cubic (MC) authentication scheme (a scheme based on an MC question), a technology disclosed in Non-Patent Literature 2 below is exemplified. As a technology related to a Syndrome Decoding (SD) authentication scheme (a scheme based on an SD question), a technology disclosed in Non-Patent Literature 3 below is exemplified. As a technology related to a Constrained Linear Equations (CLE) authentication scheme (a scheme based on a CLE question), a technology disclosed in Non-Patent Literature 4 below is exemplified. As a technology related to a Permuted Perceptrons (PP) authentication scheme (a scheme based on a PP problem), a technology disclosed in Non-Patent Literature 5 below is exemplified.